#include <iostream>
#include <vector>
#include <list>
#include <ctime>

using namespace std;

double range(pair<double,double> a, pair<double,double> b)
{
	return sqrt(pow(a.first - b.first , 2) + pow(a.second - b.second, 2));
}

void prime(vector<pair<double,double>>& points,vector<int>& answer)
{
	int n = points.size();
	int completeVerts = 1;

	vector <list<int>> mstGrph(n);
	vector <bool> used(n);
	vector <int> pred(n,-1);
	vector <double> minRange(n,std::numeric_limits<double>::infinity());

	minRange[0] = 0;
	for( int i = 0; i < n; ++i) {
		int v = -1;
		for( int j = 0; j < n; ++j)
			if(!used[j] && (v == -1 || minRange[j] < minRange[v]))
				v = j;
		used[v] = true;
		if (pred[v] != -1) {
			completeVerts++;
			mstGrph[v].push_back(pred[v]);
			mstGrph[pred[v]].push_back(v);
			if (completeVerts % 100 == 0)
				cout<<completeVerts<<endl;
		}

		for( int j = 0; j < n; ++j)
			if (range(points[v],points[j]) < minRange[j]) {
				minRange[j] = range(points[v],points[j]);
				pred[j] = v;
			}
	}
		
	vector<int> cycle;

	int tmpVert = 0;
	
	while( !mstGrph[tmpVert].empty() ) {
		cycle.push_back(tmpVert);
		int tmp = tmpVert;
		tmpVert = mstGrph[tmpVert].back();
		mstGrph[tmp].pop_back();
	}

	/*tmpVert = mstGrph[tmpVert].back();
	int tmpPred = 0;
	cycle.push_back(tmpPred);
	cycle.push_back(tmpVert);
	bool haveWay = true;

	while(haveWay) {
		int minCosRight = 2;
		int maxCosRight = -2;
		haveWay = false;
		for(std::list<int>::const_iterator it = mstGrph[tmpVert].begin(); it != mstGrph[tmpVert].end(); ++it) {
			if ( (points[tmpVert].first - points[tmpPred].first)*(points[*it].second - points[tmpVert].second) - 
				(points[tmpVert].second - points[tmpPred].second)*(points[*it].first - points[tmpVert].first) > 0) {
			}
		}
	}*/

	vector<bool> visitedVerts (n,false);

	answer.clear();

	for(vector<int>::iterator it = cycle.begin(); it != cycle.end(); ++it) 
		if (!visitedVerts[*it]) {
			answer.push_back(*it);
			visitedVerts[*it] = true;
		}
}

void generateGraph(vector<pair<double,double>>& graph) {
    vector<pair<double,double>> start_points(100);
	graph.resize(10000);

	srand(time(0));

    for (int i = 0; i < 100; ++i) {
        double d1 = 1.0 - (double)(rand()) / (RAND_MAX + 1);
        double COS = cos(6.2831853 * d1);
        double LOG = log(d1);

		start_points[i].first = 100 * COS * sqrt(-2 * LOG);
		start_points[i].second = 10 * sqrt(1.0 - COS * COS) * sqrt(-2 * LOG);
    }

    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            double d2 = 1.0 - (double)(rand()) / (RAND_MAX + 1);
            double COS = cos(6.2831853 * d2);
            double LOG = log(d2);

			graph[i * 100 + j].first = 10 * COS * sqrt(-2 * LOG) + start_points[i].first;
			graph[i * 100 + j].second = 10 * sqrt(1 - COS * COS) * sqrt(-2 * LOG) + start_points[i].second;
        }
    }
}

void closerNeighbor(vector<pair<double,double>>& points, vector<int>& answer) {

	int n = points.size();
	vector<bool> used (n);
	answer.clear();
	int tmp = 0;

	for(int i = 0; i < n; ++i) {
		double minRange = std::numeric_limits<double>::infinity();
		int closerNeigh = -1;
		for(int j = 0; j < n; ++j)
			if (!used[j] && range(points[tmp],points[j]) < minRange) {
				minRange = range(points[tmp],points[j]);
				closerNeigh = j;
			}
		tmp = closerNeigh;
		used[tmp] = true;
		answer.push_back(tmp);
	}
}



int main()
{
	
	vector<pair<double,double>> points;
	generateGraph(points);

	int n = points.size();

	vector<int> answer;
	prime(points,answer);

	double weight = 0;
	for(int i = 0; i < n - 1; ++ i)
		weight+=range(points[answer[i]],points[answer[i+1]]);
	weight+=range(points[answer[n - 1]],points[answer[0]]);
	cout<<"Prime: "<<weight<<endl;

	closerNeighbor(points,answer);
	
	weight = 0;
	for(int i = 0; i < n - 1; ++ i)
		weight+=range(points[answer[i]],points[answer[i+1]]);
	weight+=range(points[answer[n - 1]],points[answer[0]]);
	cout<<"Closer Neighbor: "<<weight<<endl;

	system("pause");
}
